package leetcode_day._2021._202109._2130;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/28 22:38
 * 路径总和 III
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * 算法：深度优先遍历
 * 两个递归
 * 以每个节点为起始点，一直遍历到叶子节点，看有没有满足的结果
 * 时间 O(n * n), 空间 O(1)
 */
public class _28_437 {

    int ans = 0, target = 0;
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        dfs1(root);
        return ans;
    }
    void dfs1(TreeNode node) {
        if (node == null) return;
        dfs2(node, node.val);
        dfs1(node.left);
        dfs1(node.right);
    }
    void dfs2(TreeNode node, int cur) {
        if (cur == target) ++ans;
        if (node.left != null) dfs2(node.left, cur + node.left.val);
        if (node.right != null) dfs2(node.right, cur + node.right.val);
    }

}
